#define _CRT_SECURE_NO_WARNINGS 1
int numDecodings(char* s) {
    int n = strlen(s);
    int* dp = (int*)malloc(sizeof(int) * n);
    memset(dp, 0, sizeof(int) * n);
    if (s[0] != '0')
        dp[0] = 1;
    if (n == 1)
        return dp[0];


    if (s[1] != '0' && s[0] != '0')
        dp[1] += 1;
    int t = (s[0] - '0') * 10 + (s[1] - '0');
    if (t >= 10 && t <= 26)
        dp[1] += 1;


    for (int i = 2; i < n; i++)
    {
        if (s[i] != '0')
            dp[i] += dp[i - 1];
        if ((s[i - 1] - '0') * 10 + (s[i] - '0') <= 26 && (s[i - 1] - '0') * 10 + (s[i] - '0') >= 10)
            dp[i] += dp[i - 2];
    }


    return dp[n - 1];
}